import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution47 {

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int[] visit=new int[nums.length];
        List<List<Integer>> ans=new ArrayList<>();
        List<Integer> temp=new ArrayList<>();
        dfs(0,temp,ans,nums,visit);
        return ans;
    }

    private void dfs(int k, List<Integer> temp, List<List<Integer>> ans, int[] nums,int[] visit) {
        if (k==nums.length){
            ans.add(new ArrayList<>(temp));
            return;
        }
        int last=-11;
        for (int i=0;i<nums.length;i++){
            if (visit[i]==0 && nums[i]!=last){
                visit[i]=1;
                last=nums[i];
                temp.add(nums[i]);
                dfs(k+1,temp,ans,nums,visit);
                visit[i]=0;
                temp.remove(temp.size()-1);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution47().permuteUnique(new int[]{1,1,2}));
    }
}
